/**
 * 
 */
package array.passed;

import java.util.HashSet;

/**
 * @author xyyi
 *
 */
public class LongestConsecutiveSequence {

	/**
	Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

	For example,
	Given [100, 4, 200, 1, 3, 2],
	The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

	Your algorithm should run in O(n) complexity.
	 */
	public int longestConsecutive(int[] num) {
		// Start typing your Java solution below
		// DO NOT write main() function
		HashSet<Integer> set = new HashSet<Integer>();
		for (int i : num) {
			set.add(i);
		}

		int longest = 1;
		for (int number : num) {
			if (set.contains(number)) {
				set.remove(number);
				int counter = 1;
				int curr = number + 1;
				while (set.contains(curr)) {
					set.remove(curr);
					curr++;
					counter++;
				}
				curr = number - 1;
				while (set.contains(curr)) {
					set.remove(curr);
					curr--;
					counter++;
				}
				longest = Math.max(longest, counter);
			}
		}

		return longest;
	}

	// best for interview
	public static int longestConsecutiveSequence(int[] num) {
		HashSet<Integer> hs = new HashSet<Integer>();
		int ret = 0;
		for (int item : num)
			hs.add(item);
		for (int i = 0; i < num.length; i++) {
			int currLength = 1;
			if (hs.contains(num[i] - 1))
				continue;
			while (hs.contains(++num[i]))
				currLength++;
			ret = currLength > ret ? currLength : ret;
		}
		return ret;
	}

	/**
	 * 
	 */
	public LongestConsecutiveSequence() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
